package com.example.leetcode.linklist;

import java.util.Stack;

/**
 *
 * 删除链表的倒数第 N 个结点
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 *
 * 输入：head = [1,2,3,4,5], n = 2
 * 输出：[1,2,3,5]
 *
 * 思路：使用栈
 *
 */
public class RemoveNthFromEnd {

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(5);

        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;

        ListNode listNode = removeNthFromEnd(listNode1, 2);
        System.out.println();
    }
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        Stack<ListNode> stack = new Stack<>();

        // 构造一个新节点
        ListNode newListNode = new ListNode(0, head);
        // 临时保存
        ListNode current = newListNode;

        // 遍历current，添加节点到栈中。此时current == null，所以需要构造一个新的节点，不然找不到头了
        while(current !=null) {
            stack.add(current);
            current = current.next;
        }

        // 删除n个元素
        for (int i = 0; i < n; i++) {
            stack.pop();
        }

        // 获取倒数n+1元素
        ListNode peek = stack.peek();
        // 删除倒数n元素
        peek.next = peek.next.next;

        // 返回头节点
        return newListNode.next;
    }
}
